#include "mySearch.h"
#include <iostream>
#include <string>
#include<stack>


using namespace std;

SSTable::SSTable()
{
	length = 0;
	origin = NULL;
}

SSTable::SSTable(int length,int* origin)
{
	this->length = length;
	this->origin = origin;
}

SSTable::~SSTable()
{
	length = 0;
	origin = NULL;
}

int SSTable::getLength()
{
	return length;
}

int* SSTable::getOrigin()
{
	return origin;
}

void SSTable::setLength(int length)
{
	this->length = length;
}

void SSTable::setOrigin(int* origin)
{
	this->origin = origin;
}

int SSTable::binSearch(int val)
{
	int low = 0;
	int high = length - 1;
	while (low <= high)
	{
		int mid = (low + high) / 2;
		if (origin[mid] == val)
			return mid;
		else if (val < origin[mid])
			high = mid - 1;
		else
			low = mid + 1;
	}
	return -1;
}

BSTreeNode::BSTreeNode()
{
	data = -1;
	lchild = NULL;
	rchild = NULL;
}

BSTreeNode::BSTreeNode(int data)
{
	this->data = data;
	lchild = NULL;
	rchild = NULL;
}

BSTreeNode::BSTreeNode(int data, BSTreeNode* lchild, BSTreeNode* rchild)
{
	this->data = data;
	this->lchild = lchild;
	this->rchild = rchild;
}

BSTreeNode::~BSTreeNode()
{
	data = -1;
	lchild = NULL;
	rchild = NULL;
}

int BSTreeNode::getData()
{
	return data;
}

BSTreeNode* BSTreeNode::getLChild()
{
	return lchild;
}

BSTreeNode* BSTreeNode::getRChild()
{
	return rchild;
}

void BSTreeNode::setData(int data)
{
	this->data = data;
}

void BSTreeNode::setLChild(BSTreeNode* lchild)
{
	this->lchild = lchild;
}

void BSTreeNode::setRChild(BSTreeNode* rchild)
{
	this->rchild = rchild;
}

BSTree::BSTree()
{
	num = 0;
	root = NULL;
}

BSTree::BSTree(int num, int* data)
{
	this->num = num;
	root = new BSTreeNode(data[0]);
	BSTreeNode* p = root;
	for (int i = 1; i < num; i++)
	{
		bool inserted = false;
		while (!inserted)
		{
			if (p->getData() > data[i])
			{
				if (p->getLChild() == NULL)
				{
					p->setLChild(new BSTreeNode(data[i]));
					inserted = true;
				}
				else
				{
					p = p->getLChild();
				}
			}
			else
			{
				if (p->getRChild() == NULL)
				{
					p->setRChild(new BSTreeNode(data[i]));
					inserted = true;
				}
				else
				{
					p = p->getRChild();
				}
			}
		}
		p = root;
	}
}

BSTree::~BSTree()
{
	num = 0;
	BSTreeNode* p = root;
	stack<BSTreeNode*> parent;
	parent.push(NULL);
	parent.push(p);
	while (parent.top() != NULL)
	{
		while (p->getLChild() != NULL || p->getRChild() != NULL)
		{
			if (p->getLChild() != NULL)
			{
				BSTreeNode* temp = p;
				p = p->getLChild();
				temp->setLChild(NULL);
				parent.push(p);
			}
			else if (p->getRChild() != NULL)
			{
				BSTreeNode* temp = p;
				p = p->getRChild();
				temp->setRChild(NULL);
				parent.push(p);
			}
		}
		parent.pop();
		delete p;
		p = parent.top();
	}
}

int BSTree::getNum()
{
	return num;
}

BSTreeNode* BSTree::getRoot()
{
	return root;
}

void BSTree::setNum(int num)
{
	this->num = num;
}

void BSTree::setRoot(BSTreeNode* root)
{
	this->root = root;
}

void printTemp(BSTreeNode* root, string& result)
{
	result += ('0'+root->getData());
	result += " ";
	if (root->getLChild() != NULL)
	{
		printTemp(root->getLChild(), result);
	}
	if (root->getRChild() != NULL)
	{
		printTemp(root->getRChild(), result);
	}
}

string BSTree::printTree()
{
	string result = "";
	printTemp(root, result);
	return result;
}

bool BSTree::searchNode(int val){
	BSTreeNode* p = root;
	bool found = false;
	while (!found)
	{
		if (p->getData() > val)
		{
			if (p->getLChild() == NULL)
			{
				break;
			}
			else
			{
				p = p->getLChild();
			}
		}
		else if (p->getData() < val)
		{
			if (p->getRChild() == NULL)
			{
				break;
			}
			else
			{
				p = p->getRChild();
			}
		}
		else
		{
			found = true;
		}
	}
	return found;
}


bool BSTree::addNode(int val)
{
	BSTreeNode* p = root;
	bool found = false;
	while (!found)
	{
		if (p->getData() > val)
		{
			if (p->getLChild() == NULL)
			{
				p->setLChild(new BSTreeNode(val));
				break;
			}
			else
			{
				p = p->getLChild();
			}
		}
		else if (p->getData() < val)
		{
			if (p->getRChild() == NULL)
			{
				p->setRChild(new BSTreeNode(val));
				break;
			}
			else
			{
				p = p->getRChild();
			}
		}
		else
		{
			found = true;
		}
	}
	return !found;
}

bool BSTree::deleteNode(int val)
{
	bool deleted = false;
	BSTreeNode* p = root;
	BSTreeNode* q = p;
	int LR = 0;
	bool found = false;
	while (!found)
	{
		if (p->getData() > val)
		{
			if (p->getLChild() == NULL)
			{
				break;
			}
			else
			{
				q = p;
				p = p->getLChild();
				LR = 0;
			}
		}
		else if (p->getData() < val)
		{
			if (p->getRChild() == NULL)
			{
				break;
			}
			else
			{
				q = p;
				p = p->getRChild();
				LR = 1;
			}
		}
		else
		{
			found = true;
			if (p->getRChild() == NULL)
			{
				if (LR)
					q->setRChild(p->getLChild());
				else
					q->setLChild(p->getLChild());
				delete p;
			}
			else if (p->getLChild() == NULL)
			{
				if (LR)
					q->setRChild(p->getRChild());
				else
					q->setLChild(p->getRChild());
				delete p;
			}
			else
			{
				q = p;
				BSTreeNode* s = p->getLChild();
				while (s->getRChild() != NULL)
				{
					q = s;
					s = s->getRChild();
				}
				p->setData(s->getData());
				if (q != p)
					q->setRChild(s->getLChild());
				else
					q->setLChild(s->getLChild());
				delete s;
			}
		}
	}
	return found;
}
